package com.topscomm.mis.cbb.pm.service.impl;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    /**
     * 记录当前遍历到的节点
     */
    Deque<Integer> stack = new ArrayDeque<>();

    public List<List<Integer>> allPathsSourceTarget(List<List<Integer>> graph) {
        stack.offerLast(0);
        dfs(graph, 0, graph.size() - 1);
        return ans;
    }

    public void dfs(List<List<Integer>> graph, int start, int n) {
        // 检查该节点与最终节点是否相等，如果相等，则表明这是一个有效路径，将其假如res中
        if (start == n) {
            ans.add(new ArrayList<>(stack));
            return;
        }
        for (int y : graph.get(start)) {
            stack.offerLast(y);
            dfs(graph, y, n);
            stack.pollLast();
        }
    }
}
